//
// Created by Administrator on 2021/11/15.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * 每次都找出当前序列中最大的数字，一次翻转放到头部，再一次翻转放到尾部
     * @param arr 
     * @return 
     */
    vector<int> pancakeSort(vector<int> &arr) {
        int n = arr.size();
        vector<int> ans;
        for (int i = n - 1; i > 0; --i) {
            int j = max_element(arr.begin(), arr.begin() + i + 1) - arr.begin();
            if (j > 0) { // 不在头部，翻转一次到头部0
                ans.push_back(j + 1);
                reverse(arr.begin(), arr.begin() + j + 1);
            }
            // 再翻转到正确位置
            reverse(arr.begin(), arr.begin() + i + 1);
            ans.push_back(i + 1);
        }
        return ans;
    }
};

int main() {
    vector<int> arr{3, 2, 4, 1};
    Solution solution;
    vector<int> ans = solution.pancakeSort(arr);
    for (const int &x:ans) cout << x << endl;
    return 0;
}


